The present invention generally relates to data transmission technology for communication systems. More particular, the present invention relates to a system and a method for blind transport format detection with cyclic redundancy check.
Digital communication utilizes various data transmission methods that convert information such as voice signal into bits of digital message, and transmit the bits of information after conversion. It is common in many communication systems that the length of transmitted message blocks is not fixed, but varies from time to time. Therefore, additional information regarding the length of a transmitted message is required for the receiver so to de-block the message. However, in certain specific applications, the data rate is prohibitively low such that the transmission of additional length information becomes an inefficient burden to the overall system. An example is the AMR 12.2 kbps mode of UMTS WCDMA, in which the transmission overhead for message length may be at a maximum of 3 kbps, which is only about 25% of the 12.2 kbps data rate. Alternatively, some error correcting codes transmitted in accompanying the message bits can be employed to convey the length information. In WCDMA, cyclic redundancy check (CRC) bits affixed to the message bits have been widely applied to detect the length information of a corresponding message block. This is known as Blind Transport Format Detection (BTFD).
FIG. 1 is a block diagram of a conventional communication system using BTFD. Referring to FIG. 1, a message block of k-bit is provided, wherein the message length k is chosen from a length candidate set S={s1, s2, . . . si} with a finite set size, wherein i is an integer. The message bits are first CRC-encoded by an l-bit CRC encoder 100 and thereafter processed by an (n, l, m) convolutional encoder 102 to generate encoded data. It is noted that additional m zeros are padded after CRC-encoded message block to terminate the trellis of convolutional codes. An example of a trellis diagram of a convolutional code is illustrated in FIG. 2.
The encoded data are modulated by a modulator 104 to form a modulated frame to be transmitted through a noisy channel 106. A receiver 108 receives the modulated frame, together with noise, through the noise channel 106. As shown in FIG. 1, the receiver 108 includes a demodulator 110 to demodulate the received frame and generate a corresponding demodulated frame. The receiver 108 further includes a convolutional decoder 112 and a CRC decoder 114 so that the demodulated frame can be decoded and the unknown message length k can be determined accordingly.
Generally, a message length {circumflex over (k)} is accepted as a legitimate candidate only when the all-zero state on the decoding trellis of the convolutional code gives the smallest path metric among all nodes at the same trellis time index ({circumflex over (k)}+l+m), and meanwhile, the validity test of the CRC bits is performed and verified. FIG. 2 illustrates an example of a trellis diagram of a convolutional code, wherein the size of length set is 6 and the message length is k=s4.
The candidate message length set S={s1, s2, . . . } is known to the receiver 108 Referring to FIG. 2, if the true message length k equals si, it is most likely that the correct trellis path of the Viterbi decoder ends at the zero state at trellis time index (si+l+m). On the other hand, at the incorrect trellis path (sj+l+m) with sj≠si, the path metric value at the zero state is smaller than the maximum path metric that belongs to the correct trellis path. After the correct trellis time index (si+l+m), the input to the Viterbi decoder is purely noise and, therefore, the path metric values become random variables. The variables may be defined as follows:
                                          δ            ⁡                          (                              s                k                            )                                =                                    -              10                        ⁢                                                  ⁢                          log              ⁡                              (                                                                                                    λ                        0                                            ⁡                                              (                                                  s                          k                                                )                                                              -                                                                  λ                        min                                            ⁡                                              (                                                  s                          k                                                )                                                                                                                                                λ                        max                                            ⁡                                              (                                                  s                          k                                                )                                                              -                                                                  λ                        min                                            ⁡                                              (                                                  s                          k                                                )                                                                                            )                                                    ,                            (        1        )            
where λ0(sk), λmax(sk) and λmin(sk) are respectively zero-state, maximum, minimum path-metric values among all survivors at the targeted trellis time index (sk+l+m). The range of δ(sk) is 0≦δ(sk)≦+∞ where δ(sk)=0 if λ0(sk)=λmax(λk) and δ(sk)Δ+∞ if λ0(sk)=λmin(sk).
In a noiseless transmission, δ(k) corresponding to the true message length k always equals zero. For other surmised message length candidate, the variables may be expressed as δ(sj) with sj≠k, δ(sj)≧0 and δ(sj)=0 with probability 2−m for |sj−k|≧m.
In a noisy transmission, δ(k) is unlikely to equal zero. Accordingly, the test using the information provided by path metrics should be lessened. Otherwise, the probability of detection will not satisfy the system requirements. For message length candidate so, a convention method compares δ(si) with a threshold Δ where the threshold Δ is a design parameter. If δ(si)≦Δ, the test criterion using the information provided by path metrics is considered acceptable. The Viterbi decoder can trace back and output block with (si+l)-bit for further CRC processing.
FIG. 3 is a flow chart of a conventional BTFD method described by Y. Okumura and F. Adachi in “Variable-Rate Data Transmission with Blind Rate Detection for Coherent DS-CDMA Mobile Radio,” IEICE Trans. Commun., vol. E81-B, No. 7, July, 1998. As shown in FIG. 3, i is first reset to one and a threshold Δ is first set to a predetermined and fixed threshold Δinit at step 300. The corresponding δ(si) value is calculated according to equation (1) above for each length candidate si at step 302 and compared to the predetermined threshold Δinit at step 304. If the value of the present δ(si) is found to be greater than the threshold Δinit at step 304, the flow proceeds to step 308 to determine whether an additional length candidate is available. If there is, the flow proceeds to step 312 to increase the value i by one and then returns to step 302; otherwise, the decoding process is completed, indicating no message length is found for the received frame. If the value of the present δ(si) is found to be less than or equal to the threshold Δinit at step 304, a Viterbi decoder traces back the received frame so as to output (si+l)-bit block at step 306. The (si+l)-bit block is thereafter subject to CRC processing by a CRC decoder at step 310. If the (si+l)-bit block passes the CRC test, the decoding process is completed, indicating that a legitimate message length is found; otherwise, the flow proceeds to step 308.
FIG. 4 is a flow chart of another conventional BTFD method as described in “Multiplexing and channel coding (FDD),” 3GPP Tech. Spec., TS 25,212 V3.9.0, March 2002. In this approach, the decoding process searches from the first length candidate to the last length candidate. If more than one legitimate message lengths are found, the decoder will output the one with the lowest δ value.
As shown in FIG. 4, i is first reset to one, δmin is preset to Δinit and nend is reset to zero at step 400. The corresponding δ(si) value is calculated according to equation (1) for each length candidate si at step 402 and compared to the predetermined threshold Δinit at step 404. If the value of the present δ(si) is found to be greater than the threshold Δinit at step 404, the flow proceeds to step 408 to determine whether any additional candidate is available. If there is, the flow proceeds to step 418 to increase the value i by one and then returns to step 402; otherwise, the flow proceeds to step 416 to determine whether nend is equal to zero. If nend is found to be equal to zero, the decoding process is completed, indicating that no message length is found for the received frame; otherwise, a legitimate message length is found to be nend.
Returning to step 404, if the value of the present δ(si) is found to be less than or equal to the threshold Δinit, a Viterbi decoder traces back the received frame so as to output (si+l)-bit block at step 406. The (si+l)-bit block is thereafter subject to CRC processing by a CRC decoder at step 410. If the (si+l)-bit block does not pass the CRC test, the flow proceeds to step 408 for further processing. If the (si+l)-bit block passes the CRC test at step 410, the present value of δ(si) is compared to δmin at step 412. If δ(si)<δmin, a legitimate message length with better δ is found, δmin is therefore set to the present value of δ(si), nend is set to si, at step 414 and the flow proceeds to step 408. If δ(si) is found to be not less than δmin at step 412, a legitimate message length is found but the present legitimate message length is not better than the previous one, and thus the flow proceeds to step 408.
When the legitimate message length is found, the present δ value is compared with the previous one at step 412. The present δ value is known before returning to previous steps of the flow and CRC decoding. Given one legitimate message block with length si and delta value δ(si) is found, it is unnecessary for other length candidates with a delta value between Δinit and δ(si) to trace back to earlier steps and provide CRC processing again. Even if the CRC test is passed, the previous message legitimate block with length si is still better than the current one.